package start;

import java.util.ArrayList;
import java.util.List;

public class Main {
    // 回溯

    // 78、子集
    List<List<Integer>> ret1; // 最后需要返回的数据
    List<Integer> path1; // 这个是吗，每一个子集
    public List<List<Integer>> subsets(int[] nums) {
        // 这个题我们用 子集里面的数据的个数，进行解决这个问题

        ret1 = new ArrayList<>();
        path1 = new ArrayList<>();

        dfs1(nums,0); //方法1
        dfs2(nums,0); //方法2
        return ret1;
    }
    // 方法2：这个题我们用 子集里面的数据的个数，进行解决这个问题
    public void dfs2(int[] nums,int pos) {
        // 这里的pos是每一层需要从哪个下标开始遍历nums的数据

        // 当每次我们进入到这个函数的时候，就是我们的一个子集
        ret1.add(new ArrayList<>(path1));

        for(int i = pos;i < nums.length;i++) {
            // 往子集里添加
            path1.add(nums[i]);
            // 添加之后我们需要递归到下一层
            dfs2(nums,i + 1); // 这里我们走的是i+1，不是pos+1
            // 回溯->恢复现场
            path1.remove(path1.size() - 1);
        }
        return;
    }
    // 方法1：利用 子集的特性，遍历每一个数据，去判断是否取这个数据
    public void dfs1(int[] nums,int pos) {
        // 这里没有需要剪枝的

        // 这里的pos是用来计数我们已经判断几个数据了，如果pos的值与nums的长度相等，就说明这个数组的整个数据已经全部判断结束了
        // pos 同样也是我们数组的下标，对应是判断到那个数据了
        // 无论 path有多少数据都需要添加进去了
        if (pos == nums.length) {
            ret1.add(new ArrayList(path1));
            return;
        }

        // 选则这个数据进入子集
        path1.add(nums[pos]);
        // 选完之后进入下一个数据进行判断
        dfs1(nums,pos + 1);
        // 下一个数据选择完后，返回之后，我们要把 现场恢复一下，也就是把path变成进入下一个数据之前的情况
        path1.remove(path1.size() - 1);

        // 不选
        // 不选则同样需要进入下一个数据，但是不需要进行任何的处理
        dfs1(nums,pos + 1);
    }


    // 46、全排列
    List<List<Integer>> ret; // 这个是返回的值
    List<Integer> path; // 这个是每个路径存入的值
    boolean[] check; // 用来判断path这个里面是否存在 对应的值，是用来剪枝用的
    public List<List<Integer>> permute(int[] nums) {
        // 初始化
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length];

        dfs(nums,0); // 在这个dfs中会把所有符合path.size() == nums.length 的值放入到 ret 中
        return ret;
    }

    public void dfs(int[] nums,int pos) {
        // 判断是否需要把 path 的值放入到 ret中，也是递归结束条件
        if (nums.length == pos) {
            ret.add(new ArrayList(path));
            return;
        }

        for(int i = 0;i < nums.length;i++) {
            // 剪枝，判断是否符合执行的条件
            if(check[i] == false) {
                path.add(nums[i]);
                check[i] = true;

                dfs(nums,pos + 1);
                // 我们在下一个位置返回到当前位置之后，再进行。恢复现场

                // 回溯 -> 恢复现场
                check[i] = false;
                path.remove(path.size() - 1);
            }
        }
        // 这是当 递归到某一个位置之后从0-最后一个值都遍历了，没有下一位置了，就会返回上一个位置了
        return;
    }
}
